#include <stdio.h>
#include <stdlib.h>

// 定义双向链表节点结构
struct Node {
    int data;           // 数据
    struct Node* prev;  // 指向前一个节点的指针
    struct Node* next;  // 指向后一个节点的指针
};

// 定义双向链表结构体
struct DoublyLinkedList {
    struct Node* head;  // 头指针，指向链表的第一个节点
    struct Node* tail;  // 尾指针，指向链表的最后一个节点
};

// 初始化双向链表
void initializeDoublyLinkedList(struct DoublyLinkedList* list) {
    list->head = NULL;
    list->tail = NULL;
}

// 插入节点到双向链表尾部
void insertNodeAtEnd(struct DoublyLinkedList* list, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }

    newNode->data = value;
    newNode->prev = list->tail;
    newNode->next = NULL;

    if (list->tail == NULL) {
        list->head = newNode;  // 如果链表为空，新节点就是头节点
    } else {
        list->tail->next = newNode;
    }

    list->tail = newNode;
}

// 查找节点
struct Node* searchNode(struct DoublyLinkedList* list, int value) {
    struct Node* current = list->head;

    while (current != NULL) {
        if (current->data == value) {
            return current; // 找到了目标节点
        }
        current = current->next;
    }

    return NULL; // 没有找到目标节点
}

// 删除节点
void deleteNode(struct DoublyLinkedList* list, int value) {
    struct Node* current = list->head;

    while (current != NULL && current->data != value) {
        current = current->next;
    }

    if (current == NULL) {
        printf("Node with value %d not found\n", value);
        return; // 没有找到要删除的节点
    }

    if (current->prev == NULL) {
        list->head = current->next; // 要删除的节点是头节点
    } else {
        current->prev->next = current->next;
    }

    if (current->next == NULL) {
        list->tail = current->prev; // 要删除的节点是尾节点
    } else {
        current->next->prev = current->prev;
    }

    free(current); // 释放要删除的节点的内存
}

// 插入节点到指定位置
void insertNodeAtPosition(struct DoublyLinkedList* list, int value, int position) {
    if (position < 0) {
        printf("Invalid position\n");
        return;
    }

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }

    newNode->data = value;

    if (position == 0) {
        newNode->prev = NULL;
        newNode->next = list->head;

        if (list->head != NULL) {
            list->head->prev = newNode;
        }

        list->head = newNode;
        if (list->tail == NULL) {
            list->tail = newNode;  // 如果链表为空，新节点就是尾节点
        }
    } else {
        struct Node* current = list->head;
        for (int i = 0; i < position - 1 && current != NULL; i++) {
            current = current->next;
        }

        if (current == NULL) {
            printf("Invalid position\n");
            free(newNode);
            return;
        }

        newNode->prev = current;
        newNode->next = current->next;

        if (current->next != NULL) {
            current->next->prev = newNode;
        }

        current->next = newNode;

        if (newNode->next == NULL) {
            list->tail = newNode;  // 如果新节点在链表末尾，更新尾指针
        }
    }
}

// 打印双向链表中的所有节点
void printDoublyLinkedList(struct DoublyLinkedList* list) {
    struct Node* current = list->head;

    printf("List: ");
    while (current != NULL) {
        printf("%d <-> ", current->data);
        current = current->next;
    }

    printf("NULL\n");
}

// 释放双向链表内存
void freeDoublyLinkedList(struct DoublyLinkedList* list) {
    struct Node* current = list->head;
    struct Node* next;

    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }

    list->head = NULL;
    list->tail = NULL;
}

int main() {
    struct DoublyLinkedList myDoublyLinkedList;
    initializeDoublyLinkedList(&myDoublyLinkedList);

    // 插入一些节点到双向链表尾部
    insertNodeAtEnd(&myDoublyLinkedList, 10);
    insertNodeAtEnd(&myDoublyLinkedList, 20);
    insertNodeAtEnd(&myDoublyLinkedList, 30);

    // 打印双向链表
    printDoublyLinkedList(&myDoublyLinkedList);

    // 查找节点
    int searchValue = 20;
    struct Node* searchResult = searchNode(&myDoublyLinkedList, searchValue);
    if (searchResult != NULL) {
        printf("Node with value %d found in the list.\n", searchValue);
    } else {
        printf("Node with value %d not found in the list.\n", searchValue);
    }

    // 删除节点
    int deleteValue = 20;
    deleteNode(&myDoublyLinkedList, deleteValue);

    printf("List after deleting node with value %d: ", deleteValue);
    printDoublyLinkedList(&myDoublyLinkedList);

    // 插入节点到指定位置
    int insertValue = 25;
    int insertPosition = 1;
    insertNodeAtPosition(&myDoublyLinkedList, insertValue, insertPosition);

    printf("List after inserting node with value %d at position %d: ", insertValue, insertPosition);
    printDoublyLinkedList(&myDoublyLinkedList);

    // 释放双向链表内存
    freeDoublyLinkedList(&myDoublyLinkedList);

    return 0;
}